Previously, we saw how Depth-First Search (DFS) can produce a topological sort. Kahn's algorithm offers a different, intuitive, and iterative approach to solve the same problem.
- The algorithm starts by identifying nodes that have no dependencies on other nodes.
- A node with no dependencies is defined as having an in-degree of zero (zero incoming edges).
- These zero in-degree nodes are the only valid starting points for the topological sequence.
- We use a queue or list to hold all nodes currently having an in-degree of zero.
- Once a node $u$ is processed, we conceptually remove it and all its outgoing edges $(u, v)$.
- Removing an edge $(u, v)$ decreases the in-degree of the target node $v$ by one.
- This decrease might create new nodes with an in-degree of zero, which are then added to the queue.
- The process repeats until all nodes are processed, resulting in the topological sort.
In-Degree
The in-degree of a vertex $v$ in a directed graph $G=(V, E)$ is the total number of edges $(u, v) \in E$ that terminate at $v$.
In Kahn's algorithm, nodes with an in-degree of 0 are the initial candidates for the topological sort.